\documentclass{article}

\usepackage{listings}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{graphicx}
\usepackage{mathpartir}
\usepackage{multirow}
\usepackage{rotating}
%\usepackage{stmaryrd}
\usepackage{fullpage} % this is useful if you have wide derivations etc.

% Some commands
\newcommand{\evals}{\Rightarrow}
\newcommand{\reduces}{\to}

\newcommand{\f}[1]{{\scriptsize {\bf \textcolor{blue}{#1\%}}}}
\newcommand{\s}[1]{{\scriptsize {\em \textcolor{red}{#1\%}}}}
\newcommand{\n}[1]{{\scriptsize {\bf ~ ~ ~ ~ }}}

\newcommand{\Opn}{{\tiny {\bf Open}}}
\newcommand{\Cls}{{\tiny {\bf Tag}}}
\newcommand{\Unn}{{\tiny {\bf Union}}}

\input{data2}

\newsavebox{\sembox}
\newlength{\semwidth}
\newlength{\boxwidth}

\newcommand{\Sem}[1]{%
\sbox{\sembox}{\ensuremath{#1}}%
\settowidth{\semwidth}{\usebox{\sembox}}%
\sbox{\sembox}{\ensuremath{\left[\usebox{\sembox}\right]}}%
\settowidth{\boxwidth}{\usebox{\sembox}}%
\addtolength{\boxwidth}{-\semwidth}%
\left[\hspace{-0.3\boxwidth}%
\usebox{\sembox}%
\hspace{-0.3\boxwidth}\right]%
}

\lstdefinestyle{Caml}{language=Caml,%
  literate={when}{{{\bf when}}}4
}

\lstdefinestyle{C++}{language=C++,%
showstringspaces=false,
  columns=fullflexible,
  escapechar=@,
  basicstyle=\sffamily,
%  commentstyle=\rmfamily\itshape,
  moredelim=**[is][\color{white}]{~}{~},
  literate={[<]}{{\textless}}1      {[>]}{{\textgreater}}1 %
           {<}{{$\langle$}}1        {>}{{$\rangle$}}1 %
           {<=}{{$\leq$}}1          {>=}{{$\geq$}}1          
           {==}{{$==$}}2            {!=}{{$\neq$}}1 %
           {=>}{{$\Rightarrow\;$}}1 {->}{{$\rightarrow{}$}}1 %
           {<:}{{$\subtype{}\ $}}1  {<-}{{$\leftarrow$}}1 %
           {e1}{{$e_1$}}2 {e2}{{$e_2$}}2 {e3}{{$e_3$}}2 {e4}{{$e_4$}}2%
           {E1}{{$E_1$}}2 {E2}{{$E_2$}}2 {E3}{{$E_3$}}2 {E4}{{$E_4$}}2%
           {m_e1}{{$m\_e_1$}}4 {m_e2}{{$m\_e_2$}}4 {m_e3}{{$m\_e_3$}}4 {m_e4}{{$m\_e_4$}}4%
           {Match}{{\emph{Match}}}5 %
           {EndMatch}{{\emph{EndMatch}}}8 %
           {Case}{{\emph{Case}}}4 %
           {Qua}{{\emph{Qua}}}3 %
           {CM}{{\emph{CM}}}2 {KS}{{\emph{KS}}}2 {KV}{{\emph{KV}}}2 
}
\lstset{style=C++}
\DeclareRobustCommand{\code}[1]{{\lstinline[breaklines=false,escapechar=@]{#1}}}
\DeclareRobustCommand{\codehaskell}[1]{{\lstinline[breaklines=false,language=Haskell]{#1}}}
\DeclareRobustCommand{\codeocaml}[1]{{\lstinline[breaklines=false,language=Caml]{#1}}}

%% grammar commands
\newcommand{\Rule}[1]{{\rmfamily\itshape{#1}}}
\newcommand{\Alt}{\ensuremath{|}}
\newcommand{\is}{$::=$}

\title{Example of evaluation and typing derivations in \LaTeX}

\begin{document}

\maketitle

\[ x^n =
	\left\{
		\begin{array}{ll}
            1         & n = 0  \\
			x         & n = 1  \\
			(x^m)^2   & n = 2m \\
			x (x^m)^2 & n = 2m+1
		\end{array}
	\right.
\]

\section{Poster}

\begin{figure*}
\begin{tabular}{@{}c@{ }l||@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}||@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}||@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}}
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 &            & \multicolumn{4}{c||}{G++/32}  & \multicolumn{4}{c||}{MS Visual C++/32} & \multicolumn{4}{c}{MS Visual C++/64} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Syntax     & \multicolumn{2}{c|}{Unified} & \multicolumn{2}{c||}{Special} & \multicolumn{2}{c|}{Unified} & \multicolumn{2}{c||}{Special} & \multicolumn{2}{c|}{Unified} & \multicolumn{2}{c}{Special} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Encoding   & \Opn  & \Cls  & \Opn  & \Cls  & \Opn  & \Cls  & \Opn  & \Cls  & \Opn  & \Cls  & \Opn  & \Cls   \\
\hline % -------------------------------------------------------------------------------------------------
\hline % -------------------------------------------------------------------------------------------------
 & Repetitive &\gwNGPp&\gwNGKp&\gwNSPp&\gwNSKp&\VwNGPp&\VwNGKp&\VwNSPp&\VwNSKp&\VxNGPp&\VxNGKp&\VxNSPp&\VxNSKp \\
 & Sequential &\gwNGPq&\gwNGKq&\gwNSPq&\gwNSKq&\VwNGPq&\VwNGKq&\VwNSPq&\VwNSKq&\VxNGPq&\VxNGKq&\VxNSPq&\VxNSKq \\
 & Random     &\gwNGPn&\gwNGKn&\gwNSPn&\gwNSKn&\VwNGPn&\VwNGKn&\VwNSPn&\VwNSKn&\VxNGPn&\VxNGKn&\VxNSPn&\VxNSKn \\
\hline % --------------------------------------------------------------------------------------------------
\multirow{3}{*}{\begin{sideways}{\tiny Forward}\end{sideways}}
 & Repetitive &\gwYGPp&\gwYGKp&\gwYSPp&\gwYSKp&\VwYGPp&\VwYGKp&\VwYSPp&\VwYSKp&\VxYGPp&\VxYGKp&\VxYSPp&\VxYSKp \\
 & Sequential &\gwYGPq&\gwYGKq&\gwYSPq&\gwYSKq&\VwYGPq&\VwYGKq&\VwYSPq&\VwYSKq&\VxYGPq&\VxYGKq&\VxYSPq&\VxYSKq \\
 & Random     &\gwYGPn&\gwYGKn&\gwYSPn&\gwYSKn&\VwYGPn&\VwYGKn&\VwYSPn&\VwYSKn&\VxYGPn&\VxYGKn&\VxYSPn&\VxYSKn \\
\hline % --------------------------------------------------------------------------------------------------
\end{tabular}
\caption{\f{42} pattern matching is faster than visitors. \s{42} visitors are 
faster than pattern matching.}
\label{poster}
\end{figure*}

\section{Evaluation 3}

\begin{figure*}
\begin{tabular}{@{}c@{ }l||@{ }r@{}@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}@{ }r@{}||@{ }r@{}@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}@{ }r@{}||@{ }r@{}@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}@{ }r@{}}
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 &            & \multicolumn{6}{c||}{G++/32}                  & \multicolumn{6}{c||}{MS Visual C++/32}        & \multicolumn{6}{c}{MS Visual C++/64}           \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Syntax     & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c}{Specialized} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Encoding   & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn   \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Repetitive &\gwNGPp&\gwNGKp&\gwNGUp&\gwNSPp&\gwNSKp&\gwNSUp&\vwNGPp&\vwNGKp&\vwNGUp&\vwNSPp&\vwNSKp&\vwNSUp&\vxNGPp&\vxNGKp&\vxNGUp&\vxNSPp&\vxNSKp&\vxNSUp \\
 & Sequential &\gwNGPq&\gwNGKq&\gwNGUq&\gwNSPq&\gwNSKq&\gwNSUq&\vwNGPq&\vwNGKq&\vwNGUq&\vwNSPq&\vwNSKq&\vwNSUq&\vxNGPq&\vxNGKq&\vxNGUq&\vxNSPq&\vxNSKq&\vxNSUq \\
 & Random     &\gwNGPn&\gwNGKn&\gwNGUn&\gwNSPn&\gwNSKn&\gwNSUn&\vwNGPn&\vwNGKn&\vwNGUn&\vwNSPn&\vwNSKn&\vwNSUn&\vxNGPn&\vxNGKn&\vxNGUn&\vxNSPn&\vxNSKn&\vxNSUn \\
\hline % ------------------------------------------------------------------------------------------------------------------------------------------
\multirow{3}{*}{\begin{sideways}{\tiny Forward}\end{sideways}}
 & Repetitive &\gwYGPp&\gwYGKp&\gwYGUp&\gwYSPp&\gwYSKp&\gwYSUp&\vwYGPp&\vwYGKp&\vwYGUp&\vwYSPp&\vwYSKp&\vwYSUp&\vxYGPp&\vxYGKp&\vxYGUp&\vxYSPp&\vxYSKp&\vxYSUp \\
 & Sequential &\gwYGPq&\gwYGKq&\gwYGUq&\gwYSPq&\gwYSKq&\gwYSUq&\vwYGPq&\vwYGKq&\vwYGUq&\vwYSPq&\vwYSKq&\vwYSUq&\vxYGPq&\vxYGKq&\vxYGUq&\vxYSPq&\vxYSKq&\vxYSUq \\
 & Random     &\gwYGPn&\gwYGKn&\gwYGUn&\gwYSPn&\gwYSKn&\gwYSUn&\vwYGPn&\vwYGKn&\vwYGUn&\vwYSPn&\vwYSKn&\vwYSUn&\vxYGPn&\vxYGKn&\vxYGUn&\vxYSPn&\vxYSKn&\vxYSUn \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 &            & \multicolumn{6}{c||}{G++/32}                  & \multicolumn{6}{c||}{MS Visual C++/32 with PGO} & \multicolumn{6}{c}{MS Visual C++/64 with PGO} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Syntax     & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c}{Specialized} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Encoding   & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn   \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Repetitive &\GwNGPp&\GwNGKp&\GwNGUp&\GwNSPp&\GwNSKp&\GwNSUp&\VwNGPp&\VwNGKp&\VwNGUp&\VwNSPp&\VwNSKp&\VwNSUp&\VxNGPp&\VxNGKp&\VxNGUp&\VxNSPp&\VxNSKp&\VxNSUp \\
 & Sequential &\GwNGPq&\GwNGKq&\GwNGUq&\GwNSPq&\GwNSKq&\GwNSUq&\VwNGPq&\VwNGKq&\VwNGUq&\VwNSPq&\VwNSKq&\VwNSUq&\VxNGPq&\VxNGKq&\VxNGUq&\VxNSPq&\VxNSKq&\VxNSUq \\
 & Random     &\GwNGPn&\GwNGKn&\GwNGUn&\GwNSPn&\GwNSKn&\GwNSUn&\VwNGPn&\VwNGKn&\VwNGUn&\VwNSPn&\VwNSKn&\VwNSUn&\VxNGPn&\VxNGKn&\VxNGUn&\VxNSPn&\VxNSKn&\VxNSUn \\
\hline % ------------------------------------------------------------------------------------------------------------------------------------------
\multirow{3}{*}{\begin{sideways}{\tiny Forward}\end{sideways}}
 & Repetitive &\GwYGPp&\GwYGKp&\GwYGUp&\GwYSPp&\GwYSKp&\GwYSUp&\VwYGPp&\VwYGKp&\VwYGUp&\VwYSPp&\VwYSKp&\VwYSUp&\VxYGPp&\VxYGKp&\VxYGUp&\VxYSPp&\VxYSKp&\VxYSUp \\
 & Sequential &\GwYGPq&\GwYGKq&\GwYGUq&\GwYSPq&\GwYSKq&\GwYSUq&\VwYGPq&\VwYGKq&\VwYGUq&\VwYSPq&\VwYSKq&\VwYSUq&\VxYGPq&\VxYGKq&\VxYGUq&\VxYSPq&\VxYSKq&\VxYSUq \\
 & Random     &\GwYGPn&\GwYGKn&\GwYGUn&\GwYSPn&\GwYSKn&\GwYSUn&\VwYGPn&\VwYGKn&\VwYGUn&\VwYSPn&\VwYSKn&\VwYSUn&\VxYGPn&\VxYGKn&\VxYGUn&\VxYSPn&\VxYSKn&\VxYSUn \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\end{tabular}
\caption{Relative performance of our pattern matching versus visitors. Numbers 
like \f{42} in bold font indicate that our pattern matching is faster than 
visitors by corresponding percentage. Numbers like \s{42} in italics font 
indicate that our solution is slower than visitors (i.e. visitors is faster than 
our solution) by corresponding percentage.}
\label{relperf}
\end{figure*}

\section{Evaluation 1}

\begin{figure*}
\begin{tabular}{@{}c@{ }l||@{ }r@{}@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}@{ }r@{}||@{ }r@{}@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}@{ }r@{}||@{ }r@{}@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}@{ }r@{}}
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 &            & \multicolumn{6}{c||}{G++/32}                  & \multicolumn{6}{c||}{MS Visual C++/32}        & \multicolumn{6}{c}{MS Visual C++/64}           \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Syntax     & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c}{Specialized} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Encoding   & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn   \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Repetitive &\n{   }&\n{   }&\n{   }&\f{101}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\s{  4}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\s{  7}&\n{   }&\n{   } \\
 & Sequential &\f{ 14}&\f{509}&\n{   }&\f{ 19}&\f{516}&\n{   }&\s{ 10}&\f{ 24}&\n{   }&\s{ 12}&\f{ 28}&\n{   }&\s{ 37}&\f{ 12}&\n{   }&\s{ 30}&\f{  5}&\n{   } \\
 & Random     &\f{  7}&\f{529}&\n{   }&\f{  8}&\f{536}&\n{   }&\s{  9}&\f{ 22}&\n{   }&\s{ 11}&\f{ 24}&\n{   }&\s{ 31}&\f{  7}&\n{   }&\s{ 36}&\f{ 13}&\n{   } \\ 
\hline % ------------------------------------------------------------------------------------------------------------------------------------------
\multirow{3}{*}{\begin{sideways}{\tiny Forward}\end{sideways}}
 & Repetitive &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   } \\
 & Sequential &\n{   }&\n{   }&\n{   }&\f{280}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{ 77}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{109}&\n{   }&\n{   } \\
 & Random     &\n{   }&\n{   }&\n{   }&\f{ 27}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\s{  6}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\s{ 18}&\n{   }&\n{   } \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 &            & \multicolumn{6}{c||}{G++/32}                  & \multicolumn{6}{c||}{MS Visual C++/32 with PGO} & \multicolumn{6}{c}{MS Visual C++/64 with PGO} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Syntax     & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c}{Specialized} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Encoding   & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn   \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Repetitive &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{ 42}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{ 12}&\n{   }&\n{   } \\
 & Sequential &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{ 22}&\f{ 47}&\n{   }&\s{  9}&\f{ 57}&\n{   }&\s{ 17}&\f{ 29}&\n{   }&\f{ 69}&\f{ 50}&\n{   } \\
 & Random     &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\s{ 10}&\f{ 38}&\n{   }&\s{ 10}&\f{ 61}&\n{   }&\s{ 13}&\f{ 21}&\n{   }&\s{ 15}&\f{ 28}&\n{   } \\ 
\hline % ------------------------------------------------------------------------------------------------------------------------------------------
\multirow{3}{*}{\begin{sideways}{\tiny Forward}\end{sideways}}
 & Repetitive &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   } \\
 & Sequential &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{147}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{118}&\n{   }&\n{   } \\
 & Random     &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{  6}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\s{  9}&\n{   }&\n{   } \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\end{tabular}
\caption{Relative performance of our pattern matching versus visitors. Numbers 
like \f{42} in bold font indicate that our pattern matching is faster than 
visitors by corresponding percentage. Numbers like \s{42} in italics font 
indicate that our solution is slower than visitors (i.e. visitors is faster than 
our solution) by corresponding percentage.}
\label{relperf}
\end{figure*}

\section{Evaluation 2}

\begin{figure*}
\begin{tabular}{@{}c@{ }l||@{ }r@{}@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}@{ }r@{}||@{ }r@{}@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}@{ }r@{}||@{ }r@{}@{ }r@{}@{ }r@{}|@{ }r@{}@{ }r@{}@{ }r@{}}
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 &            & \multicolumn{6}{c||}{G++/32}                  & \multicolumn{6}{c||}{MS Visual C++/32}        & \multicolumn{6}{c}{MS Visual C++/64}           \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Syntax     & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c}{Specialized} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Encoding   & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn   \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Repetitive &\f{ 85}&\f{329}&\n{   }&\f{ 89}&\f{274}&\n{   }&\s{  2}&\f{131}&\n{   }&\s{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\s{   }&\n{   }&\n{   } \\
 & Sequential &\f{ 15}&\f{522}&\n{   }&\f{ 18}&\f{528}&\n{   }&\s{ 10}&\f{ 61}&\n{   }&\s{   }&\f{   }&\n{   }&\s{   }&\f{   }&\n{   }&\s{   }&\f{   }&\n{   } \\
 & Random     &\f{  7}&\f{531}&\n{   }&\f{  8}&\f{537}&\n{   }&\s{  5}&\f{ 26}&\n{   }&\s{   }&\f{   }&\n{   }&\s{   }&\f{   }&\n{   }&\s{   }&\f{   }&\n{   } \\ 
\hline % ------------------------------------------------------------------------------------------------------------------------------------------
\multirow{3}{*}{\begin{sideways}{\tiny Forward}\end{sideways}}
 & Repetitive &\f{105}&\n{   }&\n{   }&\f{119}&\n{   }&\n{   }&\f{  2}&\n{   }&\n{   }&\f{  4}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   } \\
 & Sequential &\f{ 59}&\n{   }&\n{   }&\f{272}&\n{   }&\n{   }&\s{  8}&\n{   }&\n{   }&\f{133}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{   }&\n{   }&\n{   } \\
 & Random     &\f{ 28}&\n{   }&\n{   }&\f{ 22}&\n{   }&\n{   }&\f{  1}&\n{   }&\n{   }&\f{  4}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\s{   }&\n{   }&\n{   } \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 &            & \multicolumn{6}{c||}{G++/32}                  & \multicolumn{6}{c||}{MS Visual C++/32 with PGO} & \multicolumn{6}{c}{MS Visual C++/64 with PGO} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Syntax     & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c||}{Specialized} & \multicolumn{3}{c|}{Unified} & \multicolumn{3}{c}{Specialized} \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Encoding   & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn  & \Opn  & \Cls  & \Unn   \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
 & Repetitive &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{ 42}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{ 12}&\n{   }&\n{   } \\
 & Sequential &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{ 22}&\f{ 47}&\n{   }&\s{  9}&\f{ 57}&\n{   }&\s{ 17}&\f{ 29}&\n{   }&\f{ 69}&\f{ 50}&\n{   } \\
 & Random     &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\s{ 10}&\f{ 38}&\n{   }&\s{ 10}&\f{ 61}&\n{   }&\s{ 13}&\f{ 21}&\n{   }&\s{ 15}&\f{ 28}&\n{   } \\ 
\hline % ------------------------------------------------------------------------------------------------------------------------------------------
\multirow{3}{*}{\begin{sideways}{\tiny Forward}\end{sideways}}
 & Repetitive &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   } \\
 & Sequential &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{147}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{118}&\n{   }&\n{   } \\
 & Random     &\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\f{  6}&\n{   }&\n{   }&\n{   }&\n{   }&\n{   }&\s{  9}&\n{   }&\n{   } \\
\hline % -----------------------------------------------------------------------------------------------------------------------------------------
\end{tabular}
\caption{Relative performance of our pattern matching versus visitors. Numbers 
like \f{42} in bold font indicate that our pattern matching is faster than 
visitors by corresponding percentage. Numbers like \s{42} in italics font 
indicate that our solution is slower than visitors (i.e. visitors is faster than 
our solution) by corresponding percentage.}
\label{relperf}
\end{figure*}

\section{Inference rules}

\begin{mathpar}
\inferrule[Wildcard]
{}
{\Gamma\vdash \_(e) \evals true,\Gamma}

\inferrule[Variable]
{\Gamma\vdash e \evals v,\Gamma'}
{\Gamma\vdash w(e) \evals true,\Gamma'[w\leftarrow v]}

\inferrule[n+k]
{\Gamma\vdash e \evals v_1,\Gamma_1 \\ \Gamma_1\vdash \Psi_1^\oplus(v_1,c) \evals v_2,\Gamma_2 \\ \Gamma_2\vdash n(v_2) \evals b_3,\Gamma_3}
{\Gamma\vdash (n \oplus c)(e) \evals b_3,\Gamma_3}

\inferrule[n+k]
{\Gamma\vdash e \evals v_1,\Gamma_1 \\ \Gamma_1\vdash \Psi_2^\oplus(c,v_1) \evals v_2,\Gamma_2 \\ \Gamma_2\vdash n(v_2) \evals b_3,\Gamma_3}
{\Gamma\vdash (c \oplus n)(e) \evals b_3,\Gamma_3}

\inferrule[n+k]
{\Gamma\vdash e \evals v_1,\Gamma_1 \\ \Gamma_1\vdash \Psi_1^\ominus(v_1) \evals v_2,\Gamma_2 \\ \Gamma_2\vdash n(v_2) \evals b_3,\Gamma_3}
{\Gamma\vdash (\ominus n)(e) \evals b_3,\Gamma_3}

\inferrule[Guard]
{\Gamma\vdash e \evals v_1,\Gamma_1 \\ \Gamma_1\vdash \pi(v_1) \evals b_2,\Gamma_2 \\ \Gamma_2\stackrel{eval}{\vdash} x \evals b_3,\Gamma_3}
{\Gamma\vdash (\pi \models x)(e) \evals b_2 \wedge b_3,\Gamma_3}

\inferrule[Tree-Nullptr]
{\Gamma \vdash e \evals v,\Gamma_0 \\ \Gamma_0 \vdash $dynamic\_cast$\langle\tau*\rangle(v) \evals nullptr,\Gamma_1}
{\Gamma\vdash ($match$\langle\tau\rangle(\pi_1,...,\pi_k))(e) \evals nullptr,\Gamma_1}

\inferrule[Tree-False]
{\Gamma \vdash e \evals v,\Gamma_0 \\ \Gamma_0 \vdash $dynamic\_cast$\langle\tau*\rangle(v) \evals u^{\tau*},\Gamma_1 \\\\
 \Gamma_1    \vdash \Delta_1    ^\tau(v) \evals v_1,    \Gamma_1'     \\ \Gamma_1'    \vdash \pi(v_1    ) \evals true, \Gamma_2     \\\\
 \Gamma_2    \vdash \Delta_2    ^\tau(v) \evals v_2,    \Gamma_2'     \\ \Gamma_2'    \vdash \pi(v_2    ) \evals true, \Gamma_3     \\\\
 \cdots \\\\
 \Gamma_{i-1}\vdash \Delta_{i-1}^\tau(v) \evals v_{i-1},\Gamma_{i-1}' \\ \Gamma_{i-1}'\vdash \pi(v_{i-1}) \evals true, \Gamma_i     \\\\
 \Gamma_i    \vdash \Delta_i    ^\tau(v) \evals v_i,    \Gamma_i'     \\ \Gamma_i'    \vdash \pi(v_i    ) \evals false,\Gamma_{i+1} \\\\
}
{\Gamma\vdash ($match$\langle\tau\rangle(\pi_1,...,\pi_k))(e) \evals nullptr,\Gamma_{i+1}}

\inferrule[Tree-True]
{\Gamma \vdash e \evals v,\Gamma_0 \\ \Gamma_0 \vdash $dynamic\_cast$\langle\tau*\rangle(v) \evals u^{\tau*},\Gamma_1 \\\\
 \Gamma_1    \vdash \Delta_1    ^\tau(v) \evals v_1,    \Gamma_1'     \\ \Gamma_1'    \vdash \pi(v_1    ) \evals true, \Gamma_2     \\\\
 \Gamma_2    \vdash \Delta_2    ^\tau(v) \evals v_2,    \Gamma_2'     \\ \Gamma_2'    \vdash \pi(v_2    ) \evals true, \Gamma_3     \\\\
 \cdots \\\\
 \Gamma_{k-1}\vdash \Delta_{k-1}^\tau(v) \evals v_{k-1},\Gamma_{k-1}' \\ \Gamma_{k-1}'\vdash \pi(v_{k-1}) \evals true, \Gamma_k     \\\\
 \Gamma_k    \vdash \Delta_k    ^\tau(v) \evals v_k,    \Gamma_k'     \\ \Gamma_k'    \vdash \pi(v_k    ) \evals true, \Gamma_{k+1} \\\\
}
{\Gamma\vdash ($match$\langle\tau\rangle(\pi_1,...,\pi_k))(e) \evals u^{\tau*},\Gamma_{i+1}[$matched$^{\tau\&}\leftarrow*u]}
\end{mathpar}

Evaluation rules for expression templates looks as following:

\begin{mathpar}
\inferrule[Var]
{}
{\Gamma\vdash w \evals \Gamma(w),\Gamma}

\inferrule[Unary]
{\Gamma\vdash x \evals v,\Gamma_1}
{\Gamma\vdash \ominus x \evals \Sem{\ominus} v,\Gamma_1}

\inferrule[Binary]
{\Gamma\vdash x_1 \evals v_1,\Gamma_1 \\ \Gamma_1\vdash x_2 \evals v_2,\Gamma_2}
{\Gamma\vdash x_1 \oplus x_2 \evals v_1\Sem{\oplus}v_2,\Gamma_2}

\inferrule[Binary]
{\Gamma\vdash x \evals v,\Gamma_1}
{\Gamma\vdash x \oplus c \evals v\Sem{\oplus}c,\Gamma_1}

\inferrule[Binary]
{\Gamma\vdash x \evals v,\Gamma_1}
{\Gamma\vdash c \oplus x \evals c\Sem{\oplus}v,\Gamma_1}
\end{mathpar}

\section{Syntax}

\begin{center}
\begin{tabular}{rp{0em}cl}
\Rule{match statement}     & $M$     & \is{}  & \code{Match(}$e$\code{)} $\left[C s^*\right]^*$ \code{EndMatch} \\
\Rule{case clause}         & $C$     & \is{}  & \code{Case(}$T\left[,v\right]^*$\code{)} \\
                           &         & \Alt{} & \code{Qua(} $T\left[,c|v|\pi\right]^*$\code{)} \\
\Rule{target expression}   & $T$     & \is{}  & $\tau$ \Alt{} $l$ \\
\Rule{match expression}    & $m$     & \is{}  & $\pi(e)$ \\
\Rule{pattern}             & $\pi$   & \is{}  & $\_$\Alt{} $n$ \Alt{} $g$ \Alt{} $t$ \\
\Rule{tree pattern}        & $t$     & \is{}  & \code{match<}$\tau\left[,l\right]$\code{>(}$\left[c|v|\pi\right]^*$\code{)} \\
\Rule{guard pattern}       & $g$     & \is{}  & $n \models x$ \Alt{} $t \models x$ \\
\Rule{n+k pattern}         & $n$     & \is{}  & $w$ \Alt{} $n \oplus c$ \Alt{} $c \oplus n$ \Alt{} $\ominus n$ \Alt{} $(n)$ \Alt{} $\_$ \\
\Rule{wildcard pattern}    & $\_^{wildcard}$& & \\
\Rule{xt expression}       & $x$     & \is{}  & $w$ \Alt{} $x \oplus c$ \Alt{} $c \oplus x$ \Alt{} $\ominus x$ \Alt{} $(x)$ \Alt{} $x \oplus x$ \\
\Rule{xt variable}         & $w^{variable\langle\tau\rangle}$ & & \ \\
\Rule{layout}              & $l$     & \is{}  & $c^{int}$ \\
\Rule{unary operator}      &$\ominus$& $\in$  & $\lbrace*,\&,+,-,!,\sim\rbrace$ \\
\Rule{binary operator}     & $\oplus$& $\in$  & $\lbrace*,/,\%,+,-,\ll,\gg,\&,\wedge,|,$ \\
                           &         &        & $<,\leq,>,\geq,=,\neq,\&\&,||\rbrace$ \\
\Rule{type-id}             & $\tau$  &        & C++\cite[\textsection A.7]{C++0x} \\
\Rule{statement}           & $s$     &        & C++\cite[\textsection A.5]{C++0x} \\
\Rule{expression}          & $e^\tau$&        & C++\cite[\textsection A.4]{C++0x} \\
\Rule{constant-expression} & $c^\tau$&        & C++\cite[\textsection A.4]{C++0x} \\
\Rule{identifier}          & $v^\tau$&        & C++\cite[\textsection A.2]{C++0x} \\
\end{tabular}
\end{center}

\end{document}
